ফিবোনাচ্চি হিপ এবং অ্যামর্টাইজড কস্ট বিশ্লেষণ

ফিবোনাচ্চি হিপ (Fibonacci Heap)

বিবরণ: ফিবোনাচ্চি হিপ হল একটি বিশেষ ধরনের হিপ ডেটা স্ট্রাকচার যা হিপ অপারেশনগুলিকে (যেমন ইনসার্ট, ডিলিট, এবং খোঁজা) খুব কার্যকরীভাবে সম্পন্ন করে। এটি ডেটা স্ট্রাকচার তত্ত্বে ব্যবহৃত হয়, বিশেষ করে গ্রাফ অ্যালগরিদমের ক্ষেত্রে যেমন ডাইজেকস্ট্রা এবং প্রাইমস অ্যালগরিদম।

ফিবোনাচ্চি হিপের বৈশিষ্ট্য

1. এন-এরি (Amortized Cost): ফিবোনাচ্চি হিপের একটি প্রধান বৈশিষ্ট্য হল এটি বিভিন্ন অপারেশনগুলির জন্য এ্যামর্টাইজড কস্ট বিশ্লেষণ ব্যবহার করে।
2. শিশু এবং পিতার সম্পর্ক: এটি বিভিন্ন শিশুর সাথে একটি পিতার সম্পর্ক স্থাপন করে, এবং এটি প্রতিটি নোডের জন্য প্যারেন্ট এবং চাইল্ড পয়েন্টার ব্যবহার করে।
3. নোডের সংগ্রহ: নোডগুলি গাছের আকারে সংগৃহীত হয় এবং এর নোডগুলির মধ্যে একটি বিশেষ সম্পর্ক থাকে।

ফিবোনাচ্চি হিপের অপারেশন

1. ইনসার্ট (Insert): একটি নতুন নোড যোগ করে।
2. মিন (Find Minimum): সর্বনিম্ন উপাদান খুঁজে বের করে।
3. ডিলিট (Delete): সর্বনিম্ন উপাদান মুছে ফেলা।
4. ডিক্রিজ কিপ (Decrease Key): একটি কীগুলির মান কমানো।
5. ইউনিয়ন (Union): দুটি হিপকে একত্রিত করা।

এ্যামর্টাইজড কস্ট বিশ্লেষণ

এ্যামর্টাইজড কস্ট বিশ্লেষণ হল একটি পদ্ধতি যা অপারেশনগুলির গড় সময় জটিলতা নির্ধারণ করতে ব্যবহৃত হয়। এটি সস্তা এবং ব্যয়বহুল অপারেশনগুলির সাথে কাজ করে এবং একটি দৈনিক ভিত্তিতে অপারেশনগুলির গড় কস্ট নির্ধারণ করে।

ফিবোনাচ্চি হিপের জন্য কস্ট বিশ্লেষণ:

1. ইনসার্ট: O(1)
2. Find Minimum: O(1)
3. Delete Minimum: O(log n)
4. Decrease Key: O(1) (কিছু ক্ষেত্রে O(log n))
5. Union: O(1)

উদাহরণ

ফিবোনাচ্চি হিপের কাজের প্রক্রিয়া:

class FibonacciHeapNode:
    def __init__(self, key):
        self.key = key
        self.degree = 0
        self.parent = None
        self.child = None
        self.is_marked = False
        self.next = self
        self.prev = self

class FibonacciHeap:
    def __init__(self):
        self.min_node = None
        self.num_nodes = 0

    def insert(self, key):
        new_node = FibonacciHeapNode(key)
        if self.min_node is None:
            self.min_node = new_node
        else:
            # Merge the new node into the root list
            new_node.next = self.min_node
            new_node.prev = self.min_node.prev
            self.min_node.prev.next = new_node
            self.min_node.prev = new_node
            if new_node.key < self.min_node.key:
                self.min_node = new_node
        self.num_nodes += 1

    def find_minimum(self):
        return self.min_node.key if self.min_node else None

# ব্যবহার
fib_heap = FibonacciHeap()
fib_heap.insert(5)
fib_heap.insert(3)
fib_heap.insert(8)

print("Minimum node:", fib_heap.find_minimum())  # আউটপুট: Minimum node: 3

উপসংহার

ফিবোনাচ্চি হিপ একটি শক্তিশালী ডেটা স্ট্রাকচার যা হিপ অপারেশনগুলিকে কার্যকরীভাবে সম্পন্ন করতে সক্ষম। এ্যামর্টাইজড কস্ট বিশ্লেষণ দ্বারা এটি বিভিন্ন অপারেশনগুলির জন্য গড় সময় জটিলতা নির্ধারণে সহায়ক। এটি বিশেষভাবে গ্রাফ অ্যালগরিদমের জন্য উপকারী, যেখানে দ্রুততম পথ এবং মিনিমাম স্প্যানিং ট্রি তৈরি করা হয়।